package leetcode.median;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * ClassName: $39_CombinationSum
 * Description:
 * date: 2022-02-15 15:59
 *
 * @author liyifan
 */
public class $39_CombinationSum {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> combine = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        dfs(candidates, target, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target,  int index){
        if (target < 0)
            return;
        if (target == 0) {
            ans.add(new LinkedList<>(combine));
            return;
        }
        for (int i = index;i < candidates.length;i++) {
            if (candidates[i] <= target) {
                combine.add(candidates[i]);
                dfs(candidates, target - candidates[i], i);
                combine.remove(combine.size() - 1);
            }

        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates.length == 0) return res;
        fun(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }

    public void fun(List<List<Integer>> ans, List<Integer> path, int[] candidates, int target, int index) {
        if (target < 0) return;
        if (target == 0) {
            ans.add(new ArrayList<>(path));
        }

        for (int i = index;i < candidates.length;i++) {
            if (candidates[i] <= target) {
                path.add(candidates[i]);
                fun(ans, path, candidates, target - candidates[i], i);
                path.remove(path.size() - 1);
            }
        }
    }
}
